import java.util.*;

/**
 * You're given a directed graph in the form of an Adjacency Matrix Your goal is
 * to find the maximum flow given a source and sink node.
 * 
 * Remember this is a directed graph, so matrix[i][j] doesn't always equal
 * matrix[j][i]. matrix[][] is a square matrix and the number of nodes in the
 * graph is equal to the dimension of the matrix.
 * 
 * We will only be grading this based on the value you return. This means you
 * may code it however you want. (There are many different ways to implement
 * these algorithms)
 * 
 * Remember, don't change any headers like in previous homeworks.
 * 
 * * * * * * * * * * *
 * 
 * You may assume that every graph has at least two nodes, and that source and
 * sink are two valid distinct nodes. capacity[i][j] having a value of 0
 * represents that there is no edge going from vertex i to vertex j. Note that
 * cost[i][j] has no meaning if capacity[i][j] is initially 0 and it should
 * be ignored
 * 
 * * * * * * * * * * *
 * 
 * These are not necessarily algorithms we've gone over. You will have to do a
 * little research to code these.
 * 
 * * * * * * * * * * *
 * 
 * Example:
 * 
 * int[][] matrix = {{0,2}, {0,0}}; 
 * int[][] cost = {{0, 4}, {0, 0}};
 * 
 * MaxFlow.maxFlow(matrix, 0, 1) should return 2 
 * MaxFlow.minCost(matrix, cost, 0, 1) should return 8
 * 
 */
public class MaxFlow {


	private static boolean found[];
	private static int N, cap[][], flow[][], cst[][], dad[], dist[], pi[];

	private static final int INF = Integer.MAX_VALUE / 2 - 1;
	
	private static boolean search(int source, int sink) {
		Arrays.fill(found, false);
		Arrays.fill(dist, INF);
		dist[source] = 0;

		while (source != N) {
			int best = N;
			found[source] = true;
			for (int k = 0; k < N; k++) {
				if (found[k]) continue;
				if (flow[k][source] != 0) {
					int val = dist[source] + pi[source] - pi[k] - cst[k][source];
					if (dist[k] > val) {
						dist[k] = val;
						dad[k] = source;
					}
				}
				if (flow[source][k] < cap[source][k]) {
					int val = dist[source] + pi[source] - pi[k] + cst[source][k];
					if (dist[k] > val) {
						dist[k] = val;
						dad[k] = source;
					}
				}

				if (dist[k] < dist[best]) best = k;
			}
			source = best;
		}
		for (int k = 0; k < N; k++)
			pi[k] = Math.min(pi[k] + dist[k], INF);
		return found[sink];
	}


	/**
	 * Max Flow (Ford Fulkerson / Edmonds Karp)
	 * 
	 * This method returns the maximum flow through a graph.
	 * 
	 * @param capacity
	 * @param source
	 * @param sink
	 * @return
	 */
	public static int maxFlow(int[][] capacity, int source, int sink) {
		cap = capacity;

		N = cap.length;
		found = new boolean[N];
		flow = new int[N][N];
		dist = new int[N+1];
		dad = new int[N];
		pi = new int[N];

		int totflow = 0;
		while(search(source, sink)) {
			int amt = INF;
			for (int x = sink; x != source; x = dad[x])
				amt = Math.min(amt, flow[x][dad[x]] != 0 ? flow[x][dad[x]] :
					capacity[dad[x]][x] - flow[dad[x]][x]);
			for (int x = sink; x != source; x = dad[x]) {
				if (flow[x][dad[x]] != 0) {
					flow[x][dad[x]] -= amt;
				} else {
					flow[dad[x]][x] += amt;
				}
			}
			totflow += amt;
		}

		return totflow;

	}

	/**
	 * Min-Cost Max-Flow
	 * 
	 * This method returns the minimum cost of the maximum flow through a graph.
	 * The cost of putting a single unit of flow through an edge i,j is
	 * cost[i][j]
	 * 
	 * @param capacity
	 * @param cost
	 * @param source
	 * @param sink
	 * @return
	 */
	public static int minCost(int[][] capacity, int[][] cost, int source, int sink) {
		cap = capacity;
		cst = cost;

		N = cap.length;
		found = new boolean[N];
		flow = new int[N][N];
		dist = new int[N+1];
		dad = new int[N];
		pi = new int[N];

		int totcost = 0;
		while(search(source, sink)) {
			int amt = INF;
			for (int x = sink; x != source; x = dad[x])
				amt = Math.min(amt, flow[x][dad[x]] != 0 ? flow[x][dad[x]] :
					cap[dad[x]][x] - flow[dad[x]][x]);
			for (int x = sink; x != source; x = dad[x]) {
				if (flow[x][dad[x]] != 0) {
					flow[x][dad[x]] -= amt;
					totcost -= amt * cst[x][dad[x]];
				} else {
					flow[dad[x]][x] += amt;
					totcost += amt * cst[dad[x]][x];
				}
			}
		}

		return totcost;
	}
	
	/* public static void main (String args[]){
		int matrix[][] = {{0,2}, {0,0}};

		int cost1[][] = {{0, 4}, {0, 0}};

		int ret1 = MaxFlow.minCost(matrix, cost1, 0, 1);
		int ret2 = MaxFlow.maxFlow(matrix,0,1);

		System.out.println ("Min Cost: "+ret1);
		System.out.println ("Max Flow: "+ret2);
	} */

}
